<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <title>集合及其运算</title>
    <meta charset="utf-8" />
    <link rel="stylesheet" type="text/css" href="../../css/note.css" />
</head>
<body>

<h2>集合的直观概念</h2>

<p>	<b>集合</b>, 又叫做<b>集</b>或<b>搜集</b>,
	是数学中极少数不加定义的 "元概念" 之一.
	一般把集合理解为<b>具备某个性质的对象的全体</b>.
	注意这里的性质并不是随意指定的, 否则会引出矛盾 (称为悖论,
	我们在下文讨论它).
</p>

<h4>集合的性质</h4>

<ul>
	<li><b>确定性</b>.
		对于任意给定的集合 `A` 和 `a`, 一定有 `a` 属于 `A`
		和 `a` 不属于 `A` 之一成立, 分别记为 `a in A`, `a !in A`.  当 `a
		in A` 时, 称 `a` 是 `A` 的<b>元素</b>或<b>成员</b>或<b>点</b>.
		常用大写字母 `A, B, C` 等表示集合, 小写字母 `a, b, c` 等表示元素.
		注意集合的元素也是集合, 因而它们没有本质区别.
	</li>
	<li><b>互异性</b>. 集合中没有两个相同的元素, 或者说,
		任意元素在集合中都只出现一次. 在形式上, 有时我们会把一个集合写成
		`{x, y, x}`, `{x, x, y, y}`, 等. 它们和 `{x, y}` 是相同的集合.
	</li>
	<li><b>无序性</b>. 元素在集合中的出现次序是无关紧要的, 比如 `{1, 2,
		3}` 和 `{2, 3, 1}` 是同一个集合.
	</li>
	集合的这些特性, 下面都将通过公理来严格地刻画.
</ul>

<p class="remark">
	取消集合的互异性, 允许同一元素在集合中出现多次,
	得到的概念称为<b>多重集</b>, <b>类</b>或<b>族</b>.
</p>

<h4>集合的表示</h4>

<ol>
	由集合的确定性知, 只要能够确定集合中的元素, 也就确定了这个集合.
	一个集合可以有多种表示方式.
	<li>列举法. 如 `A = {a, b, c}`, `B = {1, 2, cdots, 10}`,
		`C = {{a}, {b}, {c}}`. 这里 `C` 是集合的集合, 与 `A` 不同.
		同理单元素集合 `{a}` 与元素 `a` 不同, 应区分对待.
	</li>
	<li>描述法. 用谓词描述集合元素的公共特征.
		`S = {x: P(x)}` 表示 `x in S` 当且仅当命题 `P(x)` 成立.
	</li>
</ol>

<h2>集合论的 ZFC 公理系统</h2>

<p>	由 E.Zermelo (1908) 首次提出公理系统的框架,
	A. Fraenkel (1922) 补充了一条取代公理图式, 再加上 Zermelo
	提出的选择公理 (choice axiom), 组成今天通用的 <b>ZFC 公理系统</b>.
	这一公理系统包括论述域、语法符号、造句规则与公理组:
</p>

<h4>论述域</h4>

<p>	我们的公理涉及的对象称为<b>集合 (set)</b>, 一般用拉丁字母 `A, B, C,
	cdots`; `a, b, c, cdots` 等来表示.
	在集合论的各种场合下, 往往有一个集合 `Omega` 包含了我们讨论的所有集合.
	称 `Omega` 为<b>全集</b>或<b>论述域</b>.
</p>

<h4>语法符号</h4>

<table>
	<tr>
		<td>逻辑等号</td>
		<td>`=`</td>
	</tr>
	<tr>
		<td>从属符号</td>
		<td>`in`</td>
	</tr>
	<tr>
		<td>逻辑连词符号</td>
		<td>`not, vv, ^^, rarr, harr`</td>
	</tr>
	<tr>
		<td>量词符号</td>
		<td>`EE, AA`</td>
	</tr>
	<tr>
		<td>分界符</td>
		<td>`(,)`</td>
	</tr>
</table>

<p>	为书写清晰起见, 引入更多的的分界符 `[], {}`. 在命题公式中, 它们与 `()`
	视为同一种符号.
</p>

<h4>造句规则</h4>

<ol>我们来规定什么样的命题 `P(x)` 才是合法的.
	<li>对论述域中的任意集合 `x, y`, 规定 `x = y`, `x in y` 都是合法语句,
		称为<b>原子语句</b>;
	</li>
	<li>若 `varphi, psi` 是合法语句, 则 `not varphi`, `varphi ^^ psi`,
		`varphi vv psi` 都是合法语句;
		由此定义, `varphi rarr psi iff not varphi vv psi` 和
		`varphi harr psi iff (varphi rarr psi) ^^ (psi rarr varphi)`
		都是合法语句.
	</li>
	<li>若 `varphi` 是合法语句, 则 `(AA x) varphi`, `(EE x) varphi`
		是合法语句;
	</li>
	<li>有限次运用上面的规则所得的句子都是合法语句.</li>
</ol>

<p>	由于 `x in y` 恒为合法语句, 所以一切集合间都可以判断从属关系.
	这就是集合的确定性.
</p>

<table>
	<tr>
		<td>语句</td>
		<td>简写</td>
	</tr>
	<tr>
		<td>`not(x in S)`</td>
		<td>`x !in S`</td>
	</tr>
	<tr>
		<td>`x in S ^^ y in S`</td>
		<td>`x, y in S`</td>
	</tr>
	<tr>
		<td>`x !in S ^^ y !in S`</td>
		<td>`x, y !in S`</td>
	</tr>
	<tr>
		<td>`EE x (x in S rarr varphi)`</td>
		<td>`EE x in S, varphi`</td>
	</tr>
	<tr>
		<td>`AA x (x in S rarr varphi)`</td>
		<td>`AA x in S, varphi`</td>
	</tr>
</table>

<h4>公理组</h4>

<ol>
	<li>存在公理 (existence axiom) 或空集公理 (empty axiom);</li>
	<li>外延公理 (extensionality axiom);</li>
	<li>配对公理 (pair axiom);</li>
	<li>并公理 (union axiom);</li>
	<li>幂集公理 (power set axiom);</li>
	<li>子集公理图式 (subset axiom schema), 又称分离公理图式 (separation
		axiom schema) 或概括公理图式 (comrehension axiom schema);
	</li>
	<li>无限公理 (infinity axiom);</li>
	<li>取代公理图式 (replacement axiom schema);</li>
	<li>选择公理 (choice axiom);</li>
	<li>基础公理 (foundation axiom) 又称正则公理 (regularity axiom).</li>
</ol>

<h3>集合的基本关系</h3>

<p class="axiom">
	<b>外延公理</b>
	两集合 `A, B` 相等当且仅当对任意 `a`, `a in A` 等价于 `a in B`:
	<span class="formula">
		`A = B iff AA a(a in A harr a in B)`.
	</span>
</p>

<ul class="definition">
	<b>集合的基本关系</b>
	<li> <b>包含</b>
		<span class="formula">
			`A sube B iff (a in A rArr a in B)
			iff AA a (a in A rarr a in B)`.
		</span>
		此时称 `A` 含于 `B`, 或 `B` 包含 `A`, 或 `A` 是 `B` 的子集;
	</li>
	<li> <b>相等</b>
		由外延公理知道.
		<span class="formula">
			`A = B iff A sube B ^^ B sube A`.
		</span>
		依上述定义, 两个集合相等当且仅当它们所含的元素相同,
		而与元素的次序和重复次数无关, 如
		`{a, b, c} = {a, c, b} = {a, b, c, b}`.
		此即集合元素的互异性与无序性.
	</li>
	<li> <b>真包含</b>
		<span class="formula">
			`A subne B iff A sub B iff A sube B ^^ A != B`.
		</span>
		此时称 `A` 真包含于 `B`, 或 `B` 真包含 `A`, 或 `A` 是 `B`
		的真子集.
	</li>
</ul>

<p>	以下几条公理肯定了几类集合的存在性, 再由外延公理,
	可保证它们的惟一性.
</p>

<h3>空集公理</h3>

<p class="axiom">
	<!--
	<b>存在公理</b> 存在集合与自身相等:
	<span class="formula">
		`EE x(x = x)`.
	</span>
	-->
	<b>空集公理</b> 存在一个不含任何元素的集合:
	<span class="formula">
		`EE E AA x (x !in E)`.
	</span>
	应用外延公理可证明这个集合 `E` 惟一, 称为<b>空集 (empty set)</b>,
	记为 `O/`.
</p>

<p class="proof">
	设 `EE O/' AA x (x !in O/')`.
	从而 `AA x`, `x in O/` 和 `x in O/'` 都为假,
	于是 `AA x(x in O/ harr x in O/')`, 即 `O/ = O/'`.
</p>

<h3>子集公理图式</h3>

<p class="axiom">
	<b>子集公理图式</b>
	设 `varphi` 是一个语句, 其中 `x` 是 `varphi` 的自由变元
	(即 `x` 没有被量词 `EE`, `AA` 所约束),
	且 `A` 不在 `varphi` 中出现. 则存在 `A` 的子集 `S`,
	使得 `S` 包含所有使 `varphi(x)` 成立的 `A` 的元素 `x`:
	<span class="formula">
		`AA A EE S AA x (x in S harr x in A ^^ varphi(x))`.
	</span>
	应用外延公理可证这个集合 `S` 是惟一的, 因此定义
	<span class="formula">
		`S := {x: x in A ^^ varphi(x)} = {x in A: varphi(x)}`.
	</span>
</p>

<p class="remark">
	子集公理图式允许我们用任何一个特征描述 (即命题)
	从一个给定集合中得到一个子集.
</p>

<p class="theorem">
	不存在一个包含任意元素的集合:
	<span class="formula">
		`AA A EE B (B !in A)`.
	</span>
</p>

<ol class="proof">
	令 `varphi(x) := x !in x`. 应用子集公理, 记
	<span class="formula">
		`B = {x in A: x !in x}`,
	</span>
	下证 `B !in A`. 我们反设 `B in A`, 则
	<li>如果 `B in B` 真, 由 `B` 定义, `(B in A) ^^ (B !in B)` 真, 于是 `B !in
		B` 真, 矛盾;
	</li>
	<li>如果 `B in B` 假, 由 `B` 定义, `(B in A) ^^ (B !in B)` 假, 由于 `B in
		A` 真, 所以 `B !in B` 假, 矛盾.
	</li>
	综上有 `B !in A`.
</ol>

<p class="remark">
	此定理的证明可以看出, 如果假定存在一个 "包罗万象" 的集合,
	亦即假定可以用任何一个特定描述来定义一个集合, 而不指定其范围的话,
	就会引出两难的矛盾, 这就是著名的 <b>Russell 悖论</b>.
	Russell 悖论的一个流行的说法是: 有一理发师,
	声称自己只给那些不给自己理发的人理发. 那么他给不给自己理发呢?
	假如他给自己理发, 按规定他应该属于那些不给自己理发的人, 一个矛盾;
	假如他不给自己理发, 则按规定, 他应该给自己理发!
</p>

<p class="remark">
	全体集合不构成集, 而是一个真类.
</p>

<h3>集合族的交与并</h3>

<p>	习惯上称集合的集合为<b>集合族</b>.</p>

<p class="definition">
	对任意非空集合 `cc A`, 存在集合 `I`, 使得 `x in I`
	当且仅当对任意 `cc A` 的元素 `A` 都有 `x in A`:
	<span class="formula">
		`AA cc A (cc A != O/ rarr EE I AA x(x in I harr AA A(A in cc A rarr x
		in A)))`.
	</span>
	由外延公理可证集合 `I` 惟一, 称为 `cc A` 的<b>交 (intersection)</b>,
	记为
	<span class="formula">
		`I = nnn cc A` `:= {x: AA A in cc A, x in A}`.
	</span>
</p>

<p class="proof">
	由 `cc A != O/`, 所以 `EE A_1 in cc A`.
	令 `varphi(x) := AA A (A in cc A rarr x in A)`. 由子集公理, 记
	<span class="formula">
		`I := {x in A_1: varphi(x)}`
		`= {x in A_1: AA A(A in cc A rarr x in A)}`.
	</span>
	于是 `x in I` 当且仅当 `x in A_1 ^^ AA A(A in cc A rarr x in A)`.
	由于 `A_1 in cc A`, 这又当且仅当 `AA A(A in cc A rarr x in A)`,
	即为所求的集合.
</p>

<p class="remark">
	注意 `A = O/` 时, 无法使用子集公理. 所以 `nnn O/` 无意义. 事实上如果
	`nnn O/` 有意义, 从逻辑上可以证明任意集合都是它的元素, 从而引出
	Russell 悖论:
	<span class="formula">
		`x in nnn O/`
		`iff AA A in O/ (x in A)`, 
	</span>
	然而 `A in O/` 为假, 所以上式恒为真. 但不存在包含任意元素的集合.
	矛盾.
</p>

<p class="axiom">
	<b>并公理</b>
	对任意集合 `cc A`, 存在集合 `U`, 使得 `x in U`
	当且仅当存在 `cc A` 的元素 `A`, 使得 `x in A`:
	<span class="formula">
		`AA cc A EE U AA x` `(x in U harr EE A(A in cc A ^^ x in A))`.
	</span>
	应用外延公理可证集合 `U` 惟一, 称为 `cc A` 的<b>并 (union)</b>, 记为
	<span class="formula">
		`U = uuu cc A` `:= {x: EE A in cc A, x in A}`.
	</span>
</p>

<h2>集合的代数运算</h2>

<h3>集合代数运算的定义</h3>

<!--
<p class="definition">
	若 `I` 是一集合, 且任意 `alpha in I` 唯一确定一个集合
	`A_alpha`, 则称集合
	<span class="formula">
		`  {A_alpha: alpha in I} := {B: (EE alpha in I) B = A_alpha}`
	</span>
	为<b>集合族</b>.
</p>
-->

<p class="axiom">
	<b>配对公理</b>
	对任意集合 `A, B`, 存在集合 `C`, 使得 `x in C` 当且仅当
	`x = A` 或 `x = B`:
	<span class="formula">
		`AA A AA B EE C` `(x in C harr x = A vv x = B)`.
	</span>
	由外延公理可证 `C` 惟一. 称 `C` 为 `A, B` 的<b>无序对 (unordered
		pair)</b>. 记为 `C = {A, B}`.<br/>
	特别, `AA x, {x, x} = {x}` 称为<b>单点集 (singleton)</b>.
</p>

<p class="definition">
	<b>两集合的交与并</b>
	对任意集合 `A, B`, 由配对公理, 存在 `C = {A, B}`, 再定义
	`A nn B := nnn C`, `A uu B := uuu C`. 于是 `A nn B`, `A uu B`
	都是惟一确定的. 可以验证,
	<span class="formula">
		`A nn B = {x: x in A ^^ x in B}`,<br/>
		`A uu B = {x: x in A vv x in B}`.
	</span>
</p>

<p class="definition">
	<b>集合的差与补</b>
	对任意集合 `A, B`, 令 `varphi(x) := x !in B`, 对 `A` 应用子集公理知,
	存在惟一的集合
	<span class="formula">
		`A\\B = A-B := {x: x in A ^^ x !in B}`,
	</span>
	称为 `A, B` 的<b>差 (difference)</b>.<br/>
	设 `X` 为全集, 对任意 `A sube X`, 称 `X\\A` 为 `A` 的<b>补集 (或余集,
	complement)</b>, 记为
	<span class="formula">
		`A^c = bar A = complement_X A := X \\ A = {x in X: x !in A}`.
	</span>
	定义集合 `A, B` 的<b>对称差</b>:
	<span class="formula">
		`A triangle B := (A \\ B) uu (B \\ A) = (A uu B) \\ (A nn B)`.
	</span>
</p>

<p class="axiom">
	<b>幂集公理</b>
	对任意集合 `X`, 都存在集合 `P`, 使得 `S in P` 当且仅当 `S sube X`:
	<span class="formula">
		`AA X EE P AA S(S in P harr S sube X)`.
	</span>
	由外延公理可证 `P` 惟一, 称为 `X` 的<b>幂集 (power set)</b>, 记为
	<span class="formula">
		`2^X = cc P(X) := {S: S sube X}`.
	</span>
	采用 `2^X` 这样的记号是因为, 若 `|X| = n`, 则 `|2^X| = 2^n`, 其中
	`|X|` 表示集合 `X` 的基数. 对有限集而言, 就是 `X` 中元素的个数.
	无限集的基数将在后面讨论.
	注意区分幂集与集合族的并这两个概念.
	<br/>
	把 `2^X` 的子集称为 `X` 的<b>子集族</b>. 如果 `tau` 是 `X` 的子集族,
	那么 `tau sube 2^X`, 即 `tau in 2^(2^X)`.
</p>

<p class="corollary">
	`P = 2^X rArr X = uuu P`.
</p>

<h3>集合的运算律</h3>

<p class="property">
	<span class="formula">
		`AA A in cc A, A sube B iff uuu cc A sube B`,<br/>
		`AA A in cc A, B sube A iff B sube nnn cc A`.
	</span>
</p>

<p class="property">
	<span class="formula">
		`(A^c)^c = A`, `quad`
		`A \\ B = A nn B^c`, `quad`
		`A = (A nn B) uu (A \\ B)`,<br/>
		`A sube B rArr B^c sube A^c`, `quad`
		`A nn B = O/ iff A sube B^c`, `quad`
		`A \\ B = O/ iff A sube B`,<br/>
		`(EE C) A triangle C = B triangle C iff A = B`,<br/>
		`(EE C) A nn C = B nn C and A uu C = B uu C iff A = B`.
	</span>
</p>

<p class="remark">
	<b>一个记号</b>
	设 `f(A)` 是关于集合 `A` 的某种运算 (交, 并, 差, 补等), 简记
	<span class="formula">
		`nnn_(A in cc A) f(A) = nnn{f(A): A in cc A}`
		`:= nnn{F: EE A in cc A, F = f(A)}`,<br/>
		`uuu_(A in cc A) f(A) = uuu{f(A): A in cc A}`
		`:= uuu{F: EE A in cc A, F = f(A)}`.
	</span>
	因此
	<span class="formula">
		`nnn cc A = nnn_(A in cc A) A`,
		`quad uuu cc A = uuu_(A in cc A) A`.
	</span>
</p>

<ol class="property">
	<li><b>交换律</b>
		<span class="formula">
			`A nn B = B nn A`, `quad A uu B = B uu A`.
		</span>
	</li>
	<li><b>结合律</b>
		<span class="formula">
			`(A nn B) nn C = A nn (B nn C)`,
			`quad (A uu B) uu C = A uu (B uu C)`.
		</span>
	</li>
	<li><b>分配律</b>
		<span class="formula">
			`(A nn B) uu C = (A uu C) nn (B uu C)`,
			`quad (A uu B) nn C = (A nn C) uu (B nn C)`,<br/>
			`(nnn cc A) uu B = nnn_(A in cc A) A uu B`,
			`quad (uuu cc A) nn B = uuu_(A in cc A) A nn B`,<br/>
			`(nnn cc A) uu (nnn cc B) = nnn_(A in cc A, B in cc B) A uu
			B`,
			`quad (uuu cc A) nn (uuu cc B) = uuu_(A in cc A, B in cc B) A
			nn B`.
		</span>
		但一般不成立
		<span class="formula">
			`uuu_(i in I) nnn_(j in J) A_(i, j)`
			`= nnn_(j in J) uuu_(i in I) A_(i, j)`.
		</span>
	</li>
	<li><b>对偶律</b>
		<span class="formula">
			`X\\(A nn B) = (X\\A) uu (X\\B)`,
			`quad X\\(A uu B) = (X\\A) nn (X\\B)`,<br/>
			`X\\nnn cc A = uuu_(A in cc A) X\\A`,
			`quad X\\uuu cc A = nnn_(A in cc A) X\\A`.
		</span>
	</li>
	<li><b>De Morgan 公式</b>
		<span class="formula">
			`(A nn B)^c = A^c uu B^c`,
			`quad (A uu B)^c = A^c nn B^c`,<br/>
			`(nnn cc A)^c = uuu_(A in cc A) A^c`,
			`quad (uuu cc A)^c = nnn_(A in cc A) A^c`.
		</span>
	</li>
</ol>

<script src="../../js/note.js?type=math"></script>
</body>
</html>
